FIG. 1 is a block diagram of a basic Motion Picture Experts Group (MPEG) encoding scheme. The video portion of MPEG-1 encoding is described in detail in International Standards Organization (ISO) document IS 11172, Part 2, “Video” Published Jan. 8, 1990. Subsequent versions of the MPEG video encoding standards (e.g., MPEG-2, MPEG-4) also exist.
If necessary, analog source data is converted by analog-to-digital converter 100 to digital data. The digital data is processed using discrete cosine transform 110. In general, a discrete cosine transform (DCT) is a technique for decomposing a block of data into a weighted sum of spatial frequencies. Each spatial frequency pattern has a corresponding coefficient, which is the amplitude used to represent the contribution of the spatial frequency pattern in the block of data being analyzed. DCT operations and the various implementations are known in the art. See, for example, William B. Pennebaker and Joan L. Mitchell, “JPEG: Still Image Data Compression Standard,” Van Nostrand Reinhold, 1993 or K. R. Rao and P. Yip, “Discrete Cosine Transform,” Academic Press, 1990.
In a typical MPEG encoding scheme, a frame of an image is divided into macroblocks. Each 16 pixel by 16 pixel macroblock (which is further divided into four 8 by 8 blocks) has 256 bytes of luminance (Y) data for the 256 pixels of the macroblock. The blue chrominance (U) and red chrominance (V) data for the pixels of the macroblock are communicated at ¼ resolution, or 64 bytes of V data and 64 byes of V data for the macroblock and filtering is used to blend pixel colors.
The macroblock data output by DCT 110 is further processed by quantization 120. A DCT coefficient is quantized by dividing the DCT coefficient by a nonzero positive integer called a quantization value and rounding the quotient to the nearest integer. See, for example, Joan L. Mitchell, et al., “MPEG Video Compression Standard,” Kluwer Academic Publishers, 1996, pages 46–49. The quantized macroblock coefficients are converted from a two-dimensional format (e.g., 16×16 block) to a one-dimensional sequence using a zig-zag scanning order. The sequence resulting from zig-zag transform 130 is a compressible bitstream.
The bitstream output by zig-zag transform 130 is run/level encoded by run/level encoder 140, which converts strings of zeros and non-zero coefficients output from zig-zag transform 130 into number pairs. Strings of number pairs are the MPEG-encoded bitstream that carries sufficient information to reconstruct a motion video.
Run/level encoding requires many comparison operations to determine whether a coefficient is zero or non-zero. The results of the comparison are used for conditional branch operations. In many video data streams most coefficients are zero after quantization. Because non-zero entries are used for run/level encoding the process of checking each coefficient to determine whether the coefficient is non-zero and the associated branching required is inefficient.